Leetcode 挑戰 Day 02 [9. Palindrome Number]

13th鐵人賽

meow_kai

2021-09-05 03:39:51

5111 瀏覽

分享至

9. Palindrome Number

Palindrome Number中文意思即是回文數字，這一題是相當有趣的題目，不同人寫出來的解法可能不盡相同，接下來就讓我們一起來挑戰看看這一題吧！

題目

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

題目會給我們一個整數，並希望我們能夠確認這個整數在反轉之後，與原來的是否相同，如果相同回傳true否則回傳false，另外因為像是10這樣的數字翻轉過來會變01，因此一定與原來不同，-10翻轉過來會變01-，也與要求不同，要回傳false。

轉為字串解法

我們可以藉由題目的要求，簡單判斷得知，雖然題目是給我們整數型態，但實際上如果我們能將此整數轉為字串型態，並與本身翻轉後比對是否相同，一樣可以達到題目所求。在C++與python都能運用內建函式做到這一點，但因為此方法需要較多步驟，包括轉為字串、翻轉字串、字串比對，對於電腦較熟悉數字的特性來說，是稍微慢了一點。以下展示python的程式碼。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        x = str(x)
        if x[::-1] == x:
            return True
        return False

這樣的解法在Leetcode上其實也會跑得蠻快的，但是以練習的角度，用這樣快速內建的函式來達成題目的要求，就會比較少機會思考更多其他的解法，以達到練習的效果，所以我也試著用不同的思路去看這一題。

反轉整數解法

這個解法的思路主要是希望能基於對於整數的運算，一位數一位數把原本整數的個位數，轉到最高位數，而最高位數轉到最低位數，其餘依此邏輯類推，從而達到將題目所給的整數反轉，並且在最後直接比對原先整數和反轉後整數是否相同，就能得到答案了。

但這題必須注意的是，一般在C/C++一個整數的資料佔用的空間是4個bytes也就是32bit，理論上最大也只能存到2 ^ 32 - 1的數，因此我們在翻轉整數的過程，可能會產生Overflow的問題（會出現runtime error），因此我們在設定翻轉後的整數時，可以將其設為long的資料型態，因為long是被分配到8bytes的，整整64位元，可以避免Overflow的問題。

以下是C++的程式碼

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0){
            return false;  //去除負數的情況
        }
        int m = x;  //先記住原本的x
        long y = 0;  //資料型態要設為long

        while(x != 0){  //透過迴圈和運算將整數反轉並存進y中
            y = y * 10 + x % 10; 
            x /= 10;
        }
        return m==y;
    }
};